package cn.chen.数据结构.稀疏数组;

import java.util.Arrays;

/**
 * 稀疏数组
 * 二维数组转成稀疏数组
 * 稀疏数组转成二维数组
 * */
public class SparseArray {

    public static void main(String[] args){

        // 创建一个二维数组，模仿棋盘
        int[][] arr=new int[11][11];
        arr[1][2]=1;    // 黑子
        arr[2][3]=2;    // 白子

        for(int[] row:arr){

            for(int low:row){

                System.out.printf("%d\t",low);
            }
            System.out.println();
        }

        // 二维数组转成稀疏数组
        int[][] sparse = toSparse(arr);
        // 遍历稀疏数组
        for(int[] row:sparse){
            for(int low:row){
                System.out.printf("%d\t",low);
            }
            System.out.println();
        }


        //稀疏数组转成二维数组
        int[][] arr1=sparseTo(sparse);
        for(int[] row:arr1){

            for(int low:row){

                System.out.printf("%d\t",low);
            }
            System.out.println();
        }
    }

    // 二维数组转成稀疏数组
    // 1、遍历二维数组，有多少个有效数据sum，2、创建稀疏数组sparse[sum+1][3],3、将二位数组的有效数据赋值进入稀疏数组
    public static int[][] toSparse(int[][] arr){

        int sum=0,hang=0,lie=0;
        hang=arr.length;
        for(int[] row:arr) {
            lie=row.length;
            for (int low : row) {
                if (low != 0)
                    sum++;
            }
        }
        //创建稀疏数组
        int[][] sparse=new int[sum+1][3];
        sparse[0][0]=hang;  // 行，存放
        sparse[0][1]=lie;   // 列，存放
        sparse[0][2]=sum;   // 二维数组多少个有效数据存放

        int si=1;
        // 遍历二维数组，将有效值存放到稀疏数组中
        for(int i=0;i<arr.length;i++){
            for(int j=0;j<arr[i].length;j++){

                if(arr[i][j]!=0){

                    sparse[si][0]=i;
                    sparse[si][1]=j;
                    sparse[si][2]=arr[i][j];
                    si++;   //指针指向下一行
                }
            }
        }
        return sparse;
    }
    // 稀疏数组转成二维数组
    // 1、读取稀疏数组的第一行，创建二维数组，2、读取稀疏数组的每一行，并将数据保存在二维数组中。
    private static int[][] sparseTo(int[][] sparse) {

        // 创建二维数组
        int[][] arr=new int[sparse[0][0]][sparse[0][1]];

        // 遍历稀疏数组的每一行，将有效数据存放到二维数组中
        for(int i=1;i<sparse.length;i++){

            arr[sparse[i][0]][sparse[i][1]]=sparse[i][2];
        }
        return arr;
    }
}
